/*
 * p11584.cpp
 *
 *  Created on: 2013-10-4
 *      Author: zy
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
int n, f[1010];
bool p[1010][1010];
char a[1010];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", a + 1);
		n = strlen(a + 1);
		memset(p, 0, sizeof(p));
		for (int i = n; i >= 1; i--)
		{
			p[i][i] = 1;
			p[i][i + 1] = (a[i] == a[i + 1]);
			for (int j = i + 2; j <= n; j++)
				p[i][j] = (a[i] == a[j]) && p[i + 1][j - 1];
		}
		f[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			f[i] = 0x3f3f3f3f;
			for (int j = 0; j < i; j++)
				if (p[j + 1][i])
					f[i] = min(f[i], f[j] + 1);
		}
		printf("%d\n", f[n]);
	}
	return 0;
}
